# https://leetcode.cn/problems/special-permutations/


from typing import List
from itertools import permutations
class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        ps = permutations(nums)
        ans = 0
        for p in ps:
            for i in range(1, len(p)):
                if p[i] % p[i - 1] and p[i - 1] % p[i]:
                    break
            else:
                ans += 1
        return ans